/**
 * https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/submissions/565921043/
 * 1011. 在 D 天内送达包裹的能力
 * medium 陈贝纯 2024.09.19
 * 二分搜索
 */


class Solution {
public:
    bool check(int mid,vector<int>& weights, int days){
        int n=weights.size();
        for(int i=0;i<n;++i){
            int sum=weights[i];
            while(i<n-1&&sum+weights[i+1]<=mid){
                i++;
                sum+=weights[i];
            }
            if(sum>mid)
            return false;
            days--;
        }
        return days>=0;
    }
    int shipWithinDays(vector<int>& weights, int days) {
        int n=weights.size();
        int l=1;
        int sum=0;
        for(int i=0;i<n;++i)
        sum+=weights[i];
        int r=sum;
        int ans=0;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(check(mid,weights,days)){
                ans=mid;
                r=mid-1;
            }
            else
            l=mid+1;
        }
        return ans;
    }
};